Wavelet Matrix
#Sequences
Operations
$ [0, \sigma)の整数の列$ (a_0, a_1, \dots, a_{n-1})を扱う.
空間計算量$ n \log_2 \sigma + o(n \log \sigma)bits
$ \mathtt{new}(a_1, a_2, \dots, a_n)
与えられた列を表現する Wavelet Matrix を作成する.
時間計算量$ \Theta(n \log \sigma)
$ \mathtt{access}(i)
$ a_iを返す
時間計算量$ \Theta(\log \sigma)
$ \mathtt{rank}(v, i)
$ a_0 \dots a_{i-1}に$ vが出現する回数を返す.
時間計算量$ \Theta(\log \sigma)
$ \mathtt{select}(v, i)
$ i回目に$ vが出現するインデックスを返す.
時間計算量$ \Theta(\log \sigma)
$ \mathtt{count}(l, r, d, u)
$ a_l \dots a_{r-1}のうち$ [d, u)に含まれる要素の個数を返す.
時間計算量$ \Theta(\log \sigma)
$ \mathtt{quantile}(l, r, k)
$ a_l \dots a_{r-1}のうち$ k番目に小さい要素を返す.
時間計算量$ \Theta(\log \sigma)
Summary
静的な非負整数列を管理する簡潔データ構造.
Wavelet Tree から派生したデータ構造で, $ \sigmaが大きい時に特に効率的となる.
References
Claude, F., Navarro, G., & Ordónez, A. (2015). The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems, 47, 15-32.
Gagie, T., Puglisi, S. J., & Turpin, A. (2009, August). Range quantile queries: Another virtue of wavelet trees. In International Symposium on String Processing and Information Retrieval (pp. 1-6). Springer, Berlin, Heidelberg.
中学生にもわかるウェーブレット行列 - アスペ日記
Notes
競技プログラミングにおいては, succinct ではなく compact でも十分な場合が多い.
ビットベクトルの$ \mathtt{select}は$ \omega(1)の実装が普通使用されている.
Implementations
Rust: noshi91/wavelet_matrix
Problems
$ \mathtt{quantile}